package middle;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 * 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    class Solution {
        int[] pre;
        Map<Integer, Integer> map = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            pre = preorder;
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return recur(0, inorder.length-1, 0, inorder.length-1);
        }

        private TreeNode recur(int is, int ie, int ps, int pe) {
            if (is > ie || ps > pe) {
                return null;
            }
            int currentNodeValue = pre[ps];
            int index = map.get(currentNodeValue);
            TreeNode currentNode = new TreeNode(currentNodeValue);
            // ps+1 => 当前结点的左孩子 就是前序遍历中的下一位数
            currentNode.left = recur(is, index-1, ps + 1, ps + (index - is));
            currentNode.right = recur(index+1, ie, ps + (index - is) + 1, pe);
            return currentNode;
        }
    }
}
